package Midium;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Solution825 {
    public static void main(String[] args) {
        System.out.println(numFriendRequests(new int[]{20, 30, 100,110,120}));
        System.out.println(numFriendRequests(new int[]{16,17,18}));
        System.out.println(numFriendRequests(new int[]{101,56,69,48,30}));
        System.out.println(numFriendRequests(new int[]{16,16,19,22,22}));
        List<Integer> ans = new ArrayList<Integer>();
        int[] ints = ans.stream().mapToInt(Integer::valueOf).toArray();

    }

    public static int numFriendRequests(int[] ages) {
        Arrays.sort(ages);
        int ans = 0;
        for (int i = 1; i < ages.length; i++) {
            // 若 0.5a+7  < b <= a 且 a和b必须是同龄人 ，则a可以给b发消息
            // ages[i] 代表a，寻找合适的b
            int start = 0;
            start = findIndex(ages, start, i-1,ages[i]);
            if(start >= i)
                continue;
            if (ages[i] < 100)
                ans += (i - start);
            else {
                for (int k = start; k < i; k++) {
                    if (isAgeOk(ages[i], ages[k]))
                        ans++;
                }
            }

            // 相同年龄可以互相通话
            if (ages[i] == ages[i - 1]) {
                ans++;
            }
        }
        return ans;
    }

    public static boolean isAgeOk(int A, int B) {
        if (A < 100 && B > 100) {
            return false;
        }
        return true;
    }

    // 二分法找到刚好比0.5a+7大的下标
    public static int findIndex(int[] ages,int start, int end, int target) {
        target = target / 2 + 7;
        int i = start, j = end;
        while (i <= j) {
            int mid = (j - i) / 2 + i;
            if (ages[mid] == target) {
                mid++;
                while(ages[mid]!=target)
                    return mid;
            } else if (ages[mid] < target) {
                i = mid + 1;
            } else {
                j = mid - 1;
            }
        }
        return i;
    }
}
